#define _CRT_SECURE_NO_WARNINGS 1
class Solution {
public:
    int minRectanglesToCoverPoints(vector<vector<int>>& points, int w) {
        sort(points.begin(), points.end());
        int res = 0;
        int bound = -1;
        for (auto& p : points) {
            if (p[0] > bound) {
                bound = p[0] + w;
                res++;
            }
        }
        return res;
    }
};
class Solution {
public:
    string getHint(string secret, string guess) {
        int bulls = 0;
        vector<int> cntS(10), cntG(10);
        for (int i = 0; i < secret.length(); ++i) {
            if (secret[i] == guess[i]) {
                ++bulls;
            }
            else {
                ++cntS[secret[i] - '0'];
                ++cntG[guess[i] - '0'];
            }
        }
        int cows = 0;
        for (int i = 0; i < 10; ++i) {
            cows += min(cntS[i], cntG[i]);
        }
        return to_string(bulls) + "A" + to_string(cows) + "B";
    }
};

class Solution {
public:
    long long sellingWood(int m, int n, vector<vector<int>>& prices) {
        auto pair_hash = [fn = hash<int>()](const pair<int, int>& o) -> size_t {
            return (fn(o.first) << 16) ^ fn(o.second);
            };
        unordered_map<pair<int, int>, int, decltype(pair_hash)> value(0, pair_hash);

        vector<vector<long long>> memo(m + 1, vector<long long>(n + 1, -1));

        function<long long(int, int)> dfs = [&](int x, int y) -> long long {
            if (memo[x][y] != -1) {
                return memo[x][y];
            }

            long long ret = value.count({ x, y }) ? value[{x, y}] : 0;
            if (x > 1) {
                for (int i = 1; i < x; ++i) {
                    ret = max(ret, dfs(i, y) + dfs(x - i, y));
                }
            }
            if (y > 1) {
                for (int j = 1; j < y; ++j) {
                    ret = max(ret, dfs(x, j) + dfs(x, y - j));
                }
            }
            return memo[x][y] = ret;
            };

        for (int i = 0; i < prices.size(); ++i) {
            value[{prices[i][0], prices[i][1]}] = prices[i][2];
        }
        return dfs(m, n);
    }
};

